package leetcode;

/**
 * @author: feiwang_6
 * @create: 2020/7/18 21:07
 * @description: 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历(给定前序遍历与中序遍历能够唯一确定后序遍历)
 */
public class 确定二叉树后序遍历 {
    public static StringBuilder builder = new StringBuilder();

    public static void main(String[] str) {
        /*String str1 = "EKPRZHAYQNMDIBCXUJFTVSLGWO";
        String str2 = "ZRHPAKNMQDIYCUXBFJVTSEGWOL";*/
        String str1 = "FDXEAG";
        String str2 = "XDEFAG";
        middTraver(str1, str2);
        System.out.println(builder);
    }

    public static void middTraver(String str1, String str2) {
        if (str1.length() <= 0) {
            return;
        }
        String root = str1.substring(0, 1);
        int index = getIndex(str2, root);
        middTraver(str1.substring(1, index+1), str2.substring(0, index));
        middTraver(str1.substring(index + 1), str2.substring(index + 1));
        builder.append(root);
    }

    public static int getIndex(String strs, String enu) {
        char[] chars = strs.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (enu.equals(chars[i] + "")) {
                return i;
            }
        }
        return 0;
    }
}
